/*
题目: 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

https://leetcode.cn/problems/palindromic-substrings
 */
public class CountSubstrings {
    // 动态规划
    public int countSubstrings(String s) {
        int n = s.length();
        int src = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true; // 单独一个字符串是回文串
            src ++;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i - j == 1 || dp[i - 1][j + 1]) { // 如果只有两个元素
                        src ++;
                        dp[i][j] = true;
                    }
                }
            }
        }

        return src;
    }
    int src = 0;
    int n = 0;

    // 双指针展开
    public int countSubstringss(String s) {
        // 双指针展开
        n = s.length();
        for (int i = 0; i < n; i++) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return src;
    }

    private void expand(String s, int left , int right) {
        while (left >= 0 && right < n) {
            if (s.charAt(left--) == s.charAt(right++)) {
                src ++;
            } else {
                break;
            }
        }
    }

}
